home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / cool / ge_cool.lha / GE_COOL2.1 / src / Tree / N_Node.h < prev    next >
C/C++ Source or Header  |  1992-05-15  |  9KB  |  213 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. // Created: MBN 07/05/89 -- Initial design
  13. // Updated: MBN 08/10/89 -- Initial implementation
  14. // Updated: MBN 08/11/89 -- Inherit from Generic
  15. // Updated: MBN 09/19/89 -- Added conditional exception handling
  16. // Updated: MBN 12/21/89 -- Added optional argument to set_compare method
  17. // Updated: MBN 02/27/90 -- Added operator= for pointer argument
  18. // Updated: MJF 03/12/90 -- Added group names to RAISE
  19. // Updated: VDN 02/21/92 -- New lite version
  20. //
  21. // The N_Node<Type,nchild>  class implements parameterized   nodes of a  static
  22. // size  for N-ary trees.   This node class  is parameterized for both the type
  23. // and some "N", the number of  subtrees each node  may have.  The constructors
  24. // for  the  N_Node<Type,nchild> class are  declared  in the public  section to
  25. // allow the user to create nodes and control  the building and structure of an
  26. // N-ary  tree where  the   ordering can have  a specific   meaning, as with an
  27. // expression tree.
  28. //
  29. // The  private data section contains  just two slots.  The  first is  a static
  30. // sized vector of "N" pointers to N_Node objects, one for  each subtree.   The
  31. // second is  a data  slot  of type Type  to hold the  value  of the data item.
  32. // There are three  public constructors for the  N-Node class.  The first takes
  33. // no arguments and initializes the pointer and data slots to NULL.  The second
  34. // takes an argument of type Type and initializes the data  slot to that value.
  35. // The  third takes a  reference to  another  N-Node object  and duplicates its
  36. // values.
  37. //
  38. // Methods are provided to set and get the node data value, determine if a node
  39. // is a leaf or the root of some subtree,  and implement member-wise assignment
  40. // from one  N-Node to another via  the overloaded operator=. In  addition, the
  41. // brackets operator is overloaded to  provided  a mechanism to efficiently get
  42. // and set individual  subtree pointers in  a specific node,  thus allowing the
  43. // user to   control  the  orgranization  and  structure   of a tree.  Finally,
  44. // insertion, and removal  methods to allow the  user to control  placement and
  45. // ordering of sub-trees of a node are available.
  46. //
  47.  
  48. #ifndef N_NODEH                    // If no definition for class
  49. #define N_NODEH
  50.  
  51. #ifndef MISCELANEOUSH        // If we have not included this file,
  52. #include <misc.h>        // include miscelaneous useful definitions.
  53. #endif
  54.  
  55. template <class Type, int nchild> CoolN_Node {
  56.   class CoolN_Node<Type,nchild>;        // Forward reference class
  57.   //class CoolN_Tree<CoolN_Node,Type,nchild>;    // Forward reference class 
  58.   class CoolN_Tree_CoolN_Node_##Type##_##nchild; // Forward reference class
  59.   typedef CoolN_Node<Type,nchild>* CoolN_Node_##Type##_##nchild##_p; //Pointer to class
  60.   typedef Boolean (*Type##_CoolN_Node_Compare)(const Type&, const Type&);
  61. };
  62.  
  63. template <class Type, int nchild>
  64. class CoolN_Node<Type,nchild> {
  65.   //friend class class CoolN_Tree<CoolN_Node,Type,nchild>;    
  66.   friend class CoolN_Tree_CoolN_Node_##Type##_##nchild;    // Friend class to access data
  67.   friend int Type##_default_CoolN_Node_compare (const Type&, const Type&);
  68.  
  69. public:
  70.   CoolN_Node<Type,nchild> ();            // Simple constructor
  71.   CoolN_Node<Type,nchild> (const Type&);    // constructor with data value
  72.   CoolN_Node<Type,nchild> (const CoolN_Node<Type,nchild>&); // Copy constructor
  73.   ~CoolN_Node<Type,nchild> ();            // Destructor
  74.  
  75.   inline void set (const Type&);        // Set node data to value
  76.   inline Type& get ();                // Get node data value
  77.   Boolean is_leaf () const;            // TRUE if node has no children
  78.   inline CoolN_Node_##Type##_##nchild##_p& operator[] (int); // Set/Get pointers
  79.   inline int num_subtrees () const;         // Number of subtree slots
  80.   
  81.   inline void set_compare (Type##_CoolN_Node_Compare = NULL); // Set compare
  82.   inline Boolean operator== (const Type&) const;     // Overload operator==
  83.   inline Boolean operator!= (const Type&) const;     // Overload operator!=
  84.   inline Boolean operator< (const Type&) const;         // Overload operator<
  85.   inline Boolean operator> (const Type&) const;         // Overload operator>
  86.   inline Boolean operator<= (const Type&) const;     // Overload operator<=
  87.   inline Boolean operator>= (const Type&) const;     // Overload operator>=
  88.  
  89.   CoolN_Node<Type,nchild>& operator= (const CoolN_Node<Type,nchild>&); // Assignment
  90.   Boolean insert_before (CoolN_Node<Type,nchild>&, int); // Insert subtree
  91.   Boolean insert_after (CoolN_Node<Type,nchild>&, int);     // Insert subtree
  92.  
  93. private:
  94.   CoolN_Node_##Type##_##nchild##_p sub_trees[nchild]; // Vector of subtree pointers
  95.   Type data;                    // Slot to hold data value
  96.   static Type##_CoolN_Node_Compare compare_s;    // Compare function for class
  97.  
  98.   CoolN_Node<Type,nchild>* copy_nodes(const CoolN_Node<Type,nchild>*) const; // Deep copy
  99.   void index_error (const char* fcn, int i);    // Raise exception
  100. };
  101.  
  102.  
  103.  
  104. // num_subtrees -- Returns number of slots available for subtrees in node
  105. // Input:          None
  106. // Output:         int length of the allocated array for Nodes
  107.  
  108. template <class Type, int nchild>
  109. inline int CoolN_Node<Type,nchild>::num_subtrees () const {
  110.   return nchild;
  111. }
  112.  
  113. // set -- Set value of data slot in node
  114. // Input: Reference to data slot value
  115. // Output: None
  116.  
  117. template <class Type, int nchild> 
  118. inline void CoolN_Node<Type,nchild>::set (const Type& value) {
  119.   this->data = value;                // Set data slot value
  120. }
  121.  
  122.  
  123. // get -- Get value of data slot in node
  124. // Input: None
  125. // Output: Reference to data slot value
  126.  
  127. template <class Type, int nchild> 
  128. inline Type& CoolN_Node<Type,nchild>::get () {
  129.   return this->data;                // Return data slot value
  130. }
  131.  
  132.  
  133. // set_compare -- Specify the comparison function to be used in logical tests
  134. //                of node data values
  135. // Input:         Pointer to a compare function
  136. // Output:        None
  137.  
  138. template <class Type, int nchild> 
  139. inline void CoolN_Node<Type,nchild>::set_compare (Type##_CoolN_Node_Compare c) {
  140.   if (c == NULL)
  141.     this->compare_s = &Type##_default_CoolN_Node_compare; // Default equality
  142.   else
  143.     this->compare_s = c;            // Else use one provided
  144. }
  145.  
  146.  
  147. // operator== -- Overload the equality operator to use the compare function
  148. // Input:        constant reference to Type value
  149. // Output:       TRUE/FALSE
  150.  
  151. template <class Type, int nchild> 
  152. inline Boolean CoolN_Node<Type,nchild>::operator== (const Type& value) const {
  153.   return ((((*this->compare_s)(this->data,value)) == 0) ? TRUE : FALSE);
  154. }
  155.  
  156.  
  157. // operator!= -- Overload the inequality operator to use the compare function
  158. // Input:        constant reference to Type value
  159. // Output:       TRUE/FALSE
  160.  
  161. template <class Type, int nchild> 
  162. inline Boolean CoolN_Node<Type,nchild>::operator!= (const Type& value) const {
  163.   return ((((*this->compare_s)(this->data,value)) == 0) ? FALSE : TRUE);
  164. }
  165.  
  166.  
  167. // operator< -- Overload the less than operator to use the compare function
  168. // Input:       constant reference to Type value
  169. // Output:      TRUE/FALSE
  170.  
  171. template <class Type, int nchild> 
  172. inline Boolean CoolN_Node<Type,nchild>::operator< (const Type& value) const {
  173.   return ((((*this->compare_s)(this->data,value)) < 0) ? TRUE : FALSE);
  174. }
  175.  
  176.  
  177. // operator> -- Overload the greater than operator to use the compare function
  178. // Input:       constant reference to Type value
  179. // Output:      TRUE/FALSE
  180.  
  181. template <class Type, int nchild> 
  182. inline Boolean CoolN_Node<Type,nchild>::operator> (const Type& value) const {
  183.   return ((((*this->compare_s)(this->data,value)) > 0) ? TRUE : FALSE);
  184. }
  185.  
  186.  
  187. // operator<= -- Overload the less than or equal operator to use the compare
  188. //               function
  189. // Input:        constant reference to Type value
  190. // Output:       TRUE/FALSE
  191.  
  192. template <class Type, int nchild> 
  193. inline Boolean CoolN_Node<Type,nchild>::operator<= (const Type& value) const {
  194.   return ((((*this->compare_s)(this->data,value)) > 0) ? FALSE : TRUE);
  195. }
  196.  
  197.  
  198. // operator>= -- Overload the greater than or equal operator to use the compare
  199. //               function
  200. // Input:        constant reference to Type value
  201. // Output:       TRUE/FALSE
  202.  
  203. template <class Type, int nchild> 
  204. inline Boolean CoolN_Node<Type,nchild>::operator>= (const Type& value) const {
  205.   return ((((*this->compare_s)(this->data,value)) < 0) ? FALSE : TRUE);
  206. }
  207.  
  208.  
  209.  
  210. #endif                        // End N_NODEH #if
  211.  
  212.  
  213.